package com.demo.datastructure.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author： ljr
 * @Description： 图
 * @Date： 2022/6/27 5:36 PM
 */
public class MyGraph {

    private final int v;

    private final LinkedList<Integer> adj[];


    public MyGraph(int num){
        this.v = num;
        adj = new LinkedList[num];
        for (int i = 0; i < num; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t){
        adj[s].add(t);
        adj[t].add(s);
    }


    public void breadthFirstSearch(int s, int t){
        if(s == t) return;
        LinkedList<Integer> list = adj[s];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        boolean[] visit = new boolean[v];
        visit[s] = true;

        int[] prevs = new int[v];
        for (int i = 0; i < prevs.length; i++) {
            prevs[i] = -1;
        }

        while (queue.size() != 0){
            int w = queue.poll();
            for (int i = 0; i < adj[w].size(); i++) {
                int num = adj[w].get(i);
                if(!visit[num]){
                    prevs[num] = w;
                    if(num == t){
                        print(prevs, s, t);
                        return;
                    }
                    visit[num] = true;
                    queue.add(num);
                }
            }
        }


    }

    private void print(int[] prevs, int s, int t) {
        if(t != s && prevs[t] != -1){
            print(prevs, s, prevs[t]);
        }
        System.out.println(t + ">");
    }


    public static void main(String[] args) {
        int[] prevs = new int[10];
        for (int i = 0; i < prevs.length; i++) {
            prevs[i] = -1;
        }
        prevs[4] = 3;
        prevs[8] = 4;
        prevs[2] = 8;
        printPrev(prevs, 3, 2);
    }

    private static void printPrev(int[] prevs, int s, int t) {
        if(t != s && prevs[t] != -1){
            printPrev(prevs, s, prevs[t]);
        }
        System.out.println(t + ">");
    }


}
